class Solution {
public:
    vector<vector<string>> results;
    vector<string> path;

    vector<vector<string>> partition(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n,false));

        for(int i = n-1; i >= 0; i--)
        {
            for(int j = i; j < n; ++j)
            {
                if(s[i] == s[j])
                {
                    if(j-i+1 <= 2 || dp[i+1][j-1])
                    {
                        dp[i][j] = true;
                    }
                }
            }
        }
        
        dfs(s, 0, dp);

        return results;
    }

    void dfs(const string& s, int start, vector<vector<bool>>& dp)
    {
        if(start >= s.size())
        {
            results.push_back(path);
            return;
        }

        for(int end = start; end < s.size(); ++end)
        {
            if(dp[start][end])
            {
                path.push_back(s.substr(start,end-start+1));
                dfs(s,end+1, dp);
                path.pop_back();
            }
        }
    }
};

class Solution {
public:
    int m = 0;
    int n = 0;
    int dx[4] = {-1,1,0,0};
    int dy[4] = {0,0,-1,1};
    bool check[10][10];
    string _word;

    bool exist(vector<vector<char>>& board, string word) {
        m = board.size();
        n = board[0].size();
        _word = word;

        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(board[i][j] == word[0])
                {
                    check[i][j] = true;
                    if(dfs(board, i, j, 1))
                    {
                        return true;
                    }
                    check[i][j] = false;
                }
            }
        }

        return false;
    }

    bool dfs(vector<vector<char>>& board, int i, int j, int wordStart)
    {
        if(wordStart == _word.size())
        {
            return true;
        }

        for(int k = 0; k < 4; ++k)
        {
            int x = i+dx[k];
            int y = j+dy[k];

            if(x>=0 && x<m && y>=0 && y<n && !check[x][y] && board[x][y]==_word[wordStart])
            {
                check[x][y] = true;
                if(dfs(board, x, y, wordStart+1))
                {
                    return true;
                }
                check[x][y] = false;
            }
        }

        return false;
    }
};


class Solution {
public:
    vector<string> results;
    string path;

    vector<string> generateParenthesis(int n) {
        dfs(n, 0, 0);

        return results;
    }

    void dfs(int n, int leftCount, int rightCount)
    {
        if(path.size() == 2*n)
        {
            results.push_back(path);
            return;
        }

        if(leftCount < n)
        {
            path.push_back('(');
            dfs(n, leftCount+1, rightCount);
            path.pop_back();
        }

        if(rightCount < leftCount)
        {
            path.push_back(')');
            dfs(n, leftCount, rightCount+1);
            path.pop_back();
        }
    }
};
